The size of certain symmetric differences of sets of integers

Abstract: Consider a set $A\subseteq \mathbb{N}$ which is finite and nonempty. Letting $\Delta$ denote the symmetric difference of sets and $k\cdot A=\{ka:a\in A\}$, it can be shown that $A\Delta (2\cdot A)$ always contains at least two elements. It also turns out that $A\Delta (2\cdot A) \Delta (3\cdot A)$ has at least three elements. Does $A\Delta (2\cdot A)\Delta\cdots \Delta (n\cdot A)$ have at least $n$ elements for all $n\in \mathbb{N}$? This question was posed by Pilz in an equivalent form involving the minimal distance of certain linear codes. If true, then this lower bound is best possible, as seen by considering $A=\{1\}$. The lower bound is also attained when $A=\{1,2,\dots,n\}$ and, in fact, for each $n$, there are arbitrarily large sets $A$ such that $A\Delta (2\cdot A)\Delta\cdots \Delta (n\cdot A)$ has exactly $n$ elements.

Pilz proved the conjecture for $n\le 6$, and it can also be proven for $n=7$ and $8$. For larger $n$, Pach and Szabó proved a lower bound of the form $n/(\log n)^{\lambda}$ for $\lambda\approx 0.22$. Until recently, this was the strongest result known, but in a recent work, we have proven the conjecture for all sufficiently large $n$. More precisely, whenever $n\ge 3^{81}$. In this talk we will outline the proof and discuss some related problems. Joint work with P. Pach.

number theory

Audience: researchers in the topic

Combinatorial and additive number theory seminar (CANT 2026)